package LeetCode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}22:42
 */
public class LeetCode219 {

    public static void main(String[] args) {
        int[] nums = {1,2,3,1,2,3};
        System.out.println(new LeetCode219().containsNearbyDuplicate(nums, 2));
    }

    //1、使用双指针O（n）的时间复杂度
    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++){
            int j = i + 1;
            while (j < nums.length){
                if (nums[i] == nums[j] && (j - i) <= k){
                    return true;
                }
                j++;
            }
        }
        return false;
    }

    //2、用散列表来维护这个kk大小的滑动窗口。
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++){
            if (set.contains(nums[i])){
                return true;
            }
            set.add(nums[i]);
            //如果set大小等于最大窗口大小,那就要开始收缩 将最左边的i-k踢除 就是将滑动窗口左边的向右移动
            if (set.size() > k){
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}
